#ifndef __LINKED_LIST_H__
#define __LINKED_LIST_H__

#include "Header.h"

template <class type>
class LinkedList
{
	//Element structure
	typedef struct _Element
	{
		type *pData;
		_Element *pNext;
		_Element *pPrev;
		_Element(type *element)
		{
			pData = element;
			pNext = pPrev = 0;
		}
		~_Element()
		{
			SAFE_DELETE(pData);

			if (pNext)
			{
				pNext->pPrev = pPrev;
			}

			if (pPrev)
			{
				pPrev->pNext = pNext;
			}
		}
	}Element;

private:
	Element *m_First;
	Element *m_Last;
	Element *m_Interate;
	Element *m_Temp;
	__uint32_ m_Size;
public:
	LinkedList()
		: m_First(0), m_Last(0), m_Interate(0), m_Temp(0),
		m_Size(0)
	{
	}

	~LinkedList()
	{
		Empty();
	}

	type *AddToEnd(type *element)
	{
		//Check input data
		if (element == 0)
			return 0;

		if (m_First == 0)	//There is no element in list
		{
			m_First = new Element(element);
			m_Last = m_First;
		}
		else    // There are elements in list
		{
			m_Last->pNext = new Element(element);
			m_Last->pNext->pPrev = m_Last;
			m_Last = m_Last->pNext;
		}

		//Increate size of list
		m_Size++;

		return m_Last->pData;
	}

	type *InsertBefore(type *element, Element *nextElement)
	{
		//Check input data
		if (element == 0)
			return 0;

		//Increate size of list
		m_Size++;

		//Get previous node of new element
		m_Temp = nextElement->pPrev;

		if (m_Temp == 0)	//Add before first node
		{
			m_First->pPrev = new Element(element);
			m_First->pPrev->pNext = m_First;
			m_First = m_First->pPrev;

			return m_First->pData;
		}
		else 
		{
			m_Temp->pNext = new Element(element);
			m_Temp->pNext->pPrev = m_Temp;
			m_Temp->pNext->pNext = nextElement;
			nextElement->pPrev = m_Temp->pNext;

			return m_Temp->pNext->pData;
		}
	}


};

#endif